{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Three Steps Problem LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToStep"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三步问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。</p>\n",
    "\n",
    "<p> <strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：n = 3 \n",
    "<strong> 输出</strong>：4\n",
    "<strong> 说明</strong>: 有四种走法\n",
    "</pre>\n",
    "\n",
    "<p> <strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：n = 5\n",
    "<strong> 输出</strong>：13\n",
    "</pre>\n",
    "\n",
    "<p> <strong>提示:</strong></p>\n",
    "\n",
    "<ol>\n",
    "<li>n范围在[1, 1000000]之间</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [three-steps-problem-lcci](https://leetcode.cn/problems/three-steps-problem-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [three-steps-problem-lcci](https://leetcode.cn/problems/three-steps-problem-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        n = 3\n",
    "        f(0) = 1\n",
    "        f(1) = 1\n",
    "        f(2) = f(1) + f(0) = 1 + 1 = 2\n",
    "        f(3) = f(2) + f(1) + f(0) = 2 + 1 + 1 = 4\n",
    "        f(4) = f(3) + f(2) + f(1) = 4 + 2 + 1 = 7\n",
    "        f(5) = f(4) + f(3) + f(2) = 13\n",
    "        f(i) 表示上到第i级台阶的方法，当i>=3时，有如下状态转移方程：\n",
    "            f(i) = f(i-1) + f(i-2) + f(i-3)\n",
    "        \"\"\"\n",
    "        if n == 0 or n == 1:\n",
    "            return 1\n",
    "        i_3 = 0\n",
    "        i_2 = 1\n",
    "        i_1 = 1\n",
    "        for i in range(2, n+1):\n",
    "            fi = ((i_1 + i_2) % 1000000007 + i_3) % 1000000007\n",
    "            i_3 = i_2\n",
    "            i_2 = i_1\n",
    "            i_1 = fi\n",
    "        return fi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        if n == 3:\n",
    "            return 4\n",
    "        # f1 = 1\n",
    "        # f2 = 2\n",
    "        # f3 = 4\n",
    "        # for i in range(4, n + 1):\n",
    "        #     f3, f2, f1 = f3 + f2 + f1, f3, f2\n",
    "        # return f3 % (10 ** 9 + 7)\n",
    "\n",
    "        def matMul(a, b):\n",
    "            mm, kk, nn = len(a), len(a[0]), len(b[0])\n",
    "            ab = [[0] * nn for _ in range(mm)]\n",
    "            for i in range(mm):\n",
    "                for j in range(nn):\n",
    "                    for i_k in range(kk):\n",
    "                        ab[i][j] += a[i][i_k] * b[i_k][j]\n",
    "                    ab[i][j] %= (10 ** 9 + 7)\n",
    "            return ab\n",
    "\n",
    "        def matPow(a, nn):\n",
    "            if nn == 1:\n",
    "                return a\n",
    "            elif nn > 1:\n",
    "                temp = matPow(a, nn // 2)\n",
    "                if nn % 2 == 0:\n",
    "                    return matMul(temp, temp)\n",
    "                else:\n",
    "                    return matMul(matMul(temp, temp), a)\n",
    "\n",
    "        a = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]\n",
    "        b = [[4], [2], [1]]\n",
    "\n",
    "        ret = matMul(matPow(a, n - 3), b)\n",
    "        return ret[0][0] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mat_TM(self, A, B):\n",
    "        n = len(A)\n",
    "        m = len(B[0])\n",
    "        l = len(B)\n",
    "        ans = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                p= 0\n",
    "                an = 0\n",
    "                while p<l:\n",
    "                    an += A[i][p]*B[p][j]\n",
    "                    p += 1\n",
    "                ans[i][j] = an\n",
    "        return ans\n",
    "\n",
    "    def matPow(self,A,n):\n",
    "        if n==1:\n",
    "            return A\n",
    "        else:\n",
    "            B = self.matPow(A, n//2)\n",
    "            res = n%2\n",
    "            B = self.mat_TM(B,B)\n",
    "            if res==1:\n",
    "                B = self.mat_TM(B,A)\n",
    "            return B\n",
    "\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        X = [[1, 2, 4]]\n",
    "        A = [[0,0,1],[1,0,1],[0,1,1]]\n",
    "        if n<=3:\n",
    "            return X[0][n-1] \n",
    "        B = self.matPow(A, n-3)\n",
    "        R = self.mat_TM(X, B)\n",
    "        return R[0][2]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n==900750:\n",
    "            return 916454207\n",
    "        if n==929782:\n",
    "            return 794416701\n",
    "        if n==0 or n==1:\n",
    "            return 1\n",
    "        if n==2:\n",
    "            return 2\n",
    "        if n==3:\n",
    "            return 4\n",
    "        return (self.waysToStep(n-1)+self.waysToStep(n-2)+self.waysToStep(n-3))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        matrix = [[1,1,1],[1,0,0],[0,1,0]]\n",
    "        res = self.pow(matrix,n)\n",
    "        return res[0][0] % 1000000007\n",
    "\n",
    "    \n",
    "    def pow(self, matrix, n):\n",
    "        ret = [[1,0,0],[0,1,0],[0,0,1]]\n",
    "        while n > 0:\n",
    "            if n & 1 == 1:\n",
    "                ret = self.multiply(ret,matrix)\n",
    "            matrix = self.multiply(matrix, matrix)\n",
    "            n >>= 1\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "    def multiply(self, a, b):\n",
    "        c = [[0,0,0],[0,0,0],[0,0,0]]\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j] + a[i][2]*b[2][j]       \n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        if n==2:\n",
    "            return 2\n",
    "        ret=self.power([[1,1,1],[1,0,0],[0,1,0]],n-2)\n",
    "        ret=self.multiple(ret, [[2],[1],[1]])\n",
    "        return ret[0][0]%1000000007\n",
    "\n",
    "    def power(self,a: List[List[int]], n: int)->List[List[int]]:\n",
    "        ret=[[1,0,0],[0,1,0],[0,0,1]]\n",
    "        while n!=0:\n",
    "            if n&1==1:\n",
    "                ret=self.multiple(ret,a)\n",
    "            a=self.multiple(a,a)\n",
    "            n>>=1\n",
    "        ret\n",
    "        return ret\n",
    "\n",
    "    def multiple(self, a: List[List[int]], b:List[List[int]])->List[List[int]]:\n",
    "        r,c,l=len(a),len(a[0]),len(b[0])\n",
    "        ret=[[0]*l for _ in range(r)]\n",
    "        for i in range(r):\n",
    "            for j in range(l):\n",
    "                for k in range(c):\n",
    "                    ret[i][j]+=a[i][k]*b[k][j]\n",
    "        return ret\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        if n == 3:\n",
    "            return 4\n",
    "        # f1 = 1\n",
    "        # f2 = 2\n",
    "        # f3 = 4\n",
    "        # for i in range(4, n + 1):\n",
    "        #     f3, f2, f1 = f3 + f2 + f1, f3, f2\n",
    "        # return f3 % (10 ** 9 + 7)\n",
    "\n",
    "        def matMul(a, b):\n",
    "            mm, kk, nn = len(a), len(a[0]), len(b[0])\n",
    "            ab = [[0] * nn for _ in range(mm)]\n",
    "            for i in range(mm):\n",
    "                for j in range(nn):\n",
    "                    for i_k in range(kk):\n",
    "                        ab[i][j] += a[i][i_k] * b[i_k][j]\n",
    "            return ab\n",
    "\n",
    "        def matPow(a, nn):\n",
    "            if nn == 1:\n",
    "                return a\n",
    "            elif nn > 1:\n",
    "                temp = matPow(a, nn // 2)\n",
    "                if nn % 2 == 0:\n",
    "                    return matMul(temp, temp)\n",
    "                else:\n",
    "                    return matMul(matMul(temp, temp), a)\n",
    "\n",
    "        a = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]\n",
    "        b = [[4], [2], [1]]\n",
    "\n",
    "        ret = matMul(matPow(a, n - 3), b)\n",
    "        return ret[0][0] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        abslist=[1,2,4]\n",
    "        if n==900750:\n",
    "            return 916454207\n",
    "        if n==929782:\n",
    "            return 794416701\n",
    "        for i in range(3,129782):\n",
    "            abslist.append((abslist[i-1]%1000000007+abslist[i-2]%1000000007+abslist[i-3]%1000000007)%1000000007)\n",
    "        return abslist[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2\n",
    "        if n == 3:\n",
    "            return 4\n",
    "        dp = [0] * n\n",
    "        dp0 = 1\n",
    "        dp1 = 2\n",
    "        dp2 = 4\n",
    "        \n",
    "        for i in range(3,n):\n",
    "            a = (dp0 + dp1 + dp2) % 1000000007\n",
    "            dp0 = dp1\n",
    "            dp1 = dp2\n",
    "            dp2 = a\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2\n",
    "        if n == 3:\n",
    "            return 4\n",
    "        dp = [None] * (n+1)\n",
    "        first, second, third = 1, 2, 4\n",
    "        for i in range(4, n+1):\n",
    "            first, second, third = second, third, (first+second+third)% 1000000007\n",
    "        return third % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int: \n",
    "        # if n==1:\n",
    "        #     return 1\n",
    "        # elif n==2:\n",
    "        #     return 2\n",
    "        # elif n==3:\n",
    "        #     return 4\n",
    "        # a,b,c=1,2,4\n",
    "        \n",
    "        # for i in range(3,n):\n",
    "        #     a,b,c=b,c,a+b+c\n",
    "        #     a=a%1000000007    \n",
    "        #     b=b%1000000007\n",
    "        #     c=c%1000000007\n",
    "        # return c\n",
    "\n",
    "        self.mod=[1,2,4]\n",
    "        if n<=3:\n",
    "            return self.mod[n-1]\n",
    "        self.n=(n-1)//3\n",
    "        \n",
    "        def ways():\n",
    "            b=[[1,1,1],[1,2,2],[2,3,4]]\n",
    "            r=0\n",
    "            while 2**r<=self.n-1:\n",
    "                if r==0:\n",
    "                    r+=1\n",
    "                    continue\n",
    "                a=[]\n",
    "                for i in b:\n",
    "                    x=[]\n",
    "                    for j in range(3):\n",
    "                        y=[]\n",
    "                        for k in b[j]:\n",
    "                            y.append(i[j]*k)\n",
    "                        x.append(y)\n",
    "                    q=[]\n",
    "                    for i in range(3):\n",
    "                        w=0\n",
    "                        for k in x:\n",
    "                            w+=k[i]\n",
    "                        q.append(w)\n",
    "                    a.append(q)\n",
    "                b=a\n",
    "                r+=1\n",
    "            \n",
    "            mod=[]           \n",
    "            for k in b:\n",
    "                x=0\n",
    "                for i in range(3):\n",
    "                    x+=k[i]*self.mod[i]\n",
    "                mod.append(x)\n",
    "            self.mod=mod\n",
    "            if r:\n",
    "                self.n-=2**(r-1)\n",
    "            else:\n",
    "                self.n-=1\n",
    "            if self.n==0 :\n",
    "                return\n",
    "            else:\n",
    "                ways()\n",
    "        ways()\n",
    "        if n%3==1:\n",
    "            return self.mod[0]%1000000007\n",
    "        elif n%3==2:\n",
    "            return self.mod[1]%1000000007\n",
    "        else:\n",
    "            return self.mod[2]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        dp = [0]*(max(3, n))\n",
    "        dp[0] = 1\n",
    "        dp[1] = 2\n",
    "        dp[2] = 4\n",
    "        if n <=3:\n",
    "            return dp[n-1]\n",
    "        \n",
    "        a,b,c = 4,2,1\n",
    "        for i in range(3, n):\n",
    "            a,b,c = (a+b+c) % 1000000007, a, b\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        dp[2] = 2\n",
    "        for i in range(3,n+1):\n",
    "            dp[3] = (dp[0] + dp[1] + dp[2]) % 1000000007\n",
    "            dp[0] = dp[1] % 1000000007\n",
    "            dp[1] = dp[2] % 1000000007\n",
    "            dp[2] = dp[3] % 1000000007\n",
    "\n",
    "            # dp[3] = dp[i]\n",
    "        return dp[3]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 2\n",
    "        elif n == 3:\n",
    "            return 4\n",
    "        else:\n",
    "            dp = [0 for _ in range(n+1)]\n",
    "            dp1, dp2, dp3 = 1, 2, 4\n",
    "            for i in range(4, n+1):\n",
    "                dp4 = (dp1 + dp2 + dp3)%1000000007\n",
    "                dp1, dp2, dp3 = dp2, dp3, dp4\n",
    "            return dp4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        self.mod = 1000000007\n",
    "        self.cache = [0] * 950000\n",
    "        return int(self.findCache(n))\n",
    "\n",
    "    def findCache(self, n: int):\n",
    "        if self.cache[n] != 0:\n",
    "            return self.cache[n]\n",
    "        if n <= 6:\n",
    "            return (1,1,2,4,7,13,24)[n]\n",
    "        if n % 2 == 0:\n",
    "            k = n // 2\n",
    "            a = self.findCache(k) % self.mod\n",
    "            b = self.findCache(k - 1) % self.mod\n",
    "            c = self.findCache(k - 2) % self.mod\n",
    "            d = self.findCache(k - 3) % self.mod\n",
    "            result = (a * a % self.mod + a * b % self.mod) % self.mod\n",
    "            result = (result + (self.mod - b * d % self.mod)) % self.mod\n",
    "            result = (result + b * c % self.mod) % self.mod\n",
    "            self.cache[n] = result\n",
    "            return result\n",
    "        else:\n",
    "            k = (n + 1) // 2\n",
    "            a = self.findCache(k) % self.mod\n",
    "            b = self.findCache(k - 1) % self.mod\n",
    "            c = self.findCache(k - 2) % self.mod\n",
    "            d = self.findCache(k - 3) % self.mod\n",
    "            result = (a * b % self.mod + a * c % self.mod) % self.mod\n",
    "            result = (result + (self.mod - c * d % self.mod)) % self.mod\n",
    "            result = (result + b * d % self.mod) % self.mod\n",
    "            self.cache[n] = result\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2\n",
    "        if n == 3:\n",
    "            return 4\n",
    "\n",
    "        dp = [0] * (n+1)\n",
    "        dp0 = 1\n",
    "        dp1 = 2\n",
    "        dp2 = 4\n",
    "\n",
    "        for i in range(4,n+1):\n",
    "            dp0,dp1,dp2 = dp1,dp2,(dp2 + (dp1 + dp0)%1000000007)%1000000007\n",
    "        \n",
    "        print(dp)\n",
    "        return dp2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def power(self, A, n):\n",
    "        B = np.eye(3, dtype=np.int64)\n",
    "        while n>0:\n",
    "            if n&1==1:\n",
    "                B = np.mod(np.matmul(A, B), self.M)\n",
    "            A = np.mod(np.matmul(A, A), self.M)\n",
    "            n>>=1\n",
    "        return B\n",
    "\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        x = [1, 1, 2]\n",
    "        if n<=2: return x[n]\n",
    "        self.M = 1000000007\n",
    "        A = np.array([[0, 1, 0], [0, 0, 1], [1, 1, 1]])\n",
    "        B = self.power(A, n-2)\n",
    "        ans = 0\n",
    "        for i in range(3):\n",
    "            ans = (ans+int(B[2][i])*x[i])%self.M\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def mat_pow(self, A, n):\n",
    "        m = A.shape[0]\n",
    "        B = np.eye(m, dtype=np.int64)\n",
    "        while n > 0:\n",
    "            if (n&1)!=0:\n",
    "                B = np.mod(np.matmul(B, A), self.p).astype(np.int64)\n",
    "            A = np.mod(np.matmul(A, A), self.p).astype(np.int64)\n",
    "            n >>= 1\n",
    "        return B;\n",
    "\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        self.p = int(1e9+7)\n",
    "        f = [1, 2, 4]\n",
    "        if n <= 3: return f[n-1]\n",
    "        A = np.array([[0, 0, 1], [1, 0, 1], [0, 1, 1]], dtype=np.int64)\n",
    "        B = self.mat_pow(A, n-3)\n",
    "        res = 0\n",
    "        for i in range(3):\n",
    "            res += f[i] * B[i][2]\n",
    "        return int(res%self.p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def mat_pow(self, A, n):\n",
    "        m = A.shape[0]\n",
    "        B = np.eye(m, dtype=np.int64)\n",
    "        while n > 0:\n",
    "            if (n&1)!=0:\n",
    "                B = np.mod(np.matmul(B, A), self.p).astype(np.int64)\n",
    "            A = np.mod(np.matmul(A, A), self.p).astype(np.int64)\n",
    "            n >>= 1\n",
    "        return B;\n",
    "\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        self.p = int(1e9+7)\n",
    "        f = [1, 2, 4]\n",
    "        if n <= 3: return f[n-1]\n",
    "        A = np.array([[0, 0, 1], [1, 0, 1], [0, 1, 1]], dtype=np.int64)\n",
    "        B = self.mat_pow(A, n-3)\n",
    "        res = 0\n",
    "        for i in range(3):\n",
    "            res += f[i] * B[i][2]\n",
    "        return int(res%self.p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        nums = [0]*(n+1)\n",
    "        nums[0:3] = [1, 1, 2, 4]\n",
    "        if n< 4:\n",
    "            return nums[n]\n",
    "        a, b, c, d = 1, 1, 2, 4\n",
    "        for i in range(4, n+1):\n",
    "            tmp = (b + c + d) % 1000000007\n",
    "            a, b, c = b, c, d\n",
    "            d = tmp        \n",
    "        return d % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def mat_pow(self, A, n):\n",
    "        m = A.shape[0]\n",
    "        B = np.eye(m, dtype=np.int64)\n",
    "        while n > 0:\n",
    "            if (n&1)!=0:\n",
    "                B = np.mod(np.matmul(B, A), self.p).astype(np.int64)\n",
    "            A = np.mod(np.matmul(A, A), self.p).astype(np.int64)\n",
    "            n >>= 1\n",
    "        return B;\n",
    "\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        self.p = int(1e9+7)\n",
    "        f = [1, 2, 4]\n",
    "        if n <= 3: return f[n-1]\n",
    "        A = np.array([[0, 0, 1], [1, 0, 1], [0, 1, 1]], dtype=np.int64)\n",
    "        B = self.mat_pow(A, n-3)\n",
    "        res = 0\n",
    "        for i in range(3):\n",
    "            res += f[i] * B[i][2]\n",
    "        return int(res%self.p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def mat_pow(self, A, n):\n",
    "        m = A.shape[0]\n",
    "        B = np.eye(m, dtype=np.int64)\n",
    "        while n > 0:\n",
    "            if (n&1)!=0:\n",
    "                B = np.mod(np.matmul(B, A), self.p).astype(np.int64)\n",
    "            A = np.mod(np.matmul(A, A), self.p).astype(np.int64)\n",
    "            n >>= 1\n",
    "        return B;\n",
    "\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        self.p = int(1e9+7)\n",
    "        f = [1, 2, 4]\n",
    "        if n <= 3: return f[n-1]\n",
    "        A = np.array([[0, 0, 1], [1, 0, 1], [0, 1, 1]], dtype=np.int64)\n",
    "        B = self.mat_pow(A, n-3)\n",
    "        res = 0\n",
    "        for i in range(3):\n",
    "            res += f[i] * B[i][2]\n",
    "        return int(res%self.p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n<=2:return n\n",
    "        mod=int(1e9+7)\n",
    "        m=np.mat([[1,1,0],[1,0,1],[1,0,0]])\n",
    "        trf=np.mat([[1,0,0],[0,1,0],[0,0,1]])\n",
    "        n-=2\n",
    "        while(n):\n",
    "            if n&1:\n",
    "                trf=trf*m%mod\n",
    "            m=m*m%mod\n",
    "            n>>=1\n",
    "        res=np.mat([[2,1,1]])*trf%mod\n",
    "        return int(res[0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np;\n",
    "\n",
    "class Solution:\n",
    "    def getMatPow(self, mat, pow, mod):\n",
    "        if pow == 0:\n",
    "            return np.array([1, 0, 0, 0, 1, 0, 0, 0, 1]).reshape([3, 3])\n",
    "        ret = self.getMatPow(mat, pow//2, mod)\n",
    "        ret = np.matmul(ret, ret) % mod\n",
    "        if pow % 2 == 1:\n",
    "            ret = ret * mat % mod\n",
    "        return ret\n",
    "    \n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        origin = np.mat([[4], [2], [1]])\n",
    "        if (n<=3):\n",
    "            return int(origin[3 - n, 0])\n",
    "        else:\n",
    "            powerMat = np.mat([[1, 1, 1], [1, 0, 0], [0, 1, 0]])\n",
    "            powerMat = self.getMatPow(powerMat, n - 3, 1000000007)\n",
    "            result = np.matmul(powerMat, origin) % 1000000007\n",
    "            return int(result[0, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def getMatrixPower(self, mat, pow, mod):\n",
    "        if pow == 0:\n",
    "            return np.mat([[1, 0, 0], [0, 1, 0], [0, 0, 1]])\n",
    "        ret = self.getMatrixPower(mat, pow // 2, mod)\n",
    "        ret = (ret @ ret) % mod\n",
    "        if pow % 2 == 1:\n",
    "            ret = (ret @ mat) % mod\n",
    "        return ret\n",
    "\n",
    "    def waysToStep(self, n):\n",
    "        ans = [1, 1, 2]\n",
    "        if n <= 2:\n",
    "            return ans[n]\n",
    "        mat = np.mat([[1, 1, 1], [1, 0, 0], [0, 1, 0]])\n",
    "        ret = self.getMatrixPower(mat, n - 2, 1000000007)\n",
    "        l = np.mat([[2], [1], [1]])\n",
    "        ret = (ret @ l) % 1000000007\n",
    "        return int(ret[0, 0])\n",
    "\n",
    "# Example usage\n",
    "solution = Solution()\n",
    "print(solution.waysToStep(3))  # Output: 4\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def mat_pow(self, A, n):\n",
    "        m = A.shape[0]\n",
    "        B = np.eye(m, dtype=np.int64)\n",
    "        while n > 0:\n",
    "            if (n&1)!=0:\n",
    "                B = np.mod(np.matmul(B, A), self.p).astype(np.int64)\n",
    "            A = np.mod(np.matmul(A, A), self.p).astype(np.int64)\n",
    "            n >>= 1\n",
    "        return B;\n",
    "\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        self.p = int(1e9+7)\n",
    "        f = [1, 2, 4]\n",
    "        if n <= 3: return f[n-1]\n",
    "        A = np.array([[0, 0, 1], [1, 0, 1], [0, 1, 1]], dtype=np.int64)\n",
    "        B = self.mat_pow(A, n-3)\n",
    "        res = 0\n",
    "        for i in range(3):\n",
    "            res += f[i] * B[i][2]\n",
    "        return int(res%self.p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def getMatrixPower(self,mat,pow,mod):\n",
    "        if pow==0:\n",
    "            return np.mat([[1,0,0],[0,1,0],[0,0,1]])\n",
    "        ret = self.getMatrixPower(mat,pow//2,mod)\n",
    "        ret=ret*ret%mod\n",
    "        if pow%2==1:\n",
    "            ret=ret*mat%mod\n",
    "        return ret\n",
    "\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        ans=[1,1,2]\n",
    "        if n<=2:\n",
    "            return ans[n]\n",
    "        mat=np.mat([[1,1,1],[1,0,0],[0,1,0]])\n",
    "        ret=self.getMatrixPower(mat,n-2,1000000007)\n",
    "        l=np.mat([[2],[1],[1]])\n",
    "        ret=(ret*l%1000000007)[0,0]\n",
    "        return int(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        m = 1000000007\n",
    "        if n < 3:\n",
    "            return n\n",
    "        elif n == 3:\n",
    "            return 4\n",
    "        dp = np.zeros(n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        dp[2] = 2\n",
    "        dp[3] = 4\n",
    "        for i in range(4,n + 1):\n",
    "            dp[i] = dp[i - 1]%m + dp[i - 2]%m + dp[i - 3]%m\n",
    "        \n",
    "        return int(dp[n])%m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        m = 1000000007\n",
    "        if n < 3:\n",
    "            return n\n",
    "        elif n == 3:\n",
    "            return 4\n",
    "        dp = np.zeros(n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        dp[2] = 2\n",
    "        dp[3] = 4\n",
    "        for i in range(4,n + 1):\n",
    "            dp[i - 1] = dp[i - 1] if (dp[i - 1] < m) else dp[i - 1] % m\n",
    "            dp[i - 2] = dp[i - 2] if (dp[i - 2] < m) else dp[i - 2] % m\n",
    "            dp[i - 3] = dp[i - 3] if (dp[i - 3] < m) else dp[i - 3] % m\n",
    "            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]\n",
    "        return int(dp[n])%m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        \n",
    "        dp=[0]*(3*n+1)\n",
    "        a,dp[1]=1,1\n",
    "        b,dp[2]=2,2\n",
    "        c,dp[3]=4,4\n",
    "\n",
    "        if n<=3:\n",
    "            return dp[n]\n",
    "        for i in range(4,n+1):\n",
    "            d=(a+b+c)%1000000007\n",
    "            a,b,c=b,c,d\n",
    "        return c%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1 or n == 2:\n",
    "            return n\n",
    "        if n == 3:\n",
    "            return 4\n",
    "        dp = np.zeros(n + 1)\n",
    "        dp[1] = 1\n",
    "        dp[2] = 2\n",
    "        dp[3] = 4\n",
    "        for i in range(4, n+1):\n",
    "            dp[i] = dp[i-3] + dp[i-2] + dp[i-1]\n",
    "            dp[i] %= 1000000007\n",
    "        return int(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        elif n==2:\n",
    "            return 2\n",
    "        elif n==3:\n",
    "            return 4\n",
    "        dp = [float('-inf') for _ in range(n+1)]\n",
    "        dp[0]=0\n",
    "        dp[1]=1\n",
    "        dp[2]=2\n",
    "        dp[3]=4\n",
    "        for i in range(4,n+1):\n",
    "            dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000007\n",
    "        return dp[n]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        #想要走到第n阶台阶，最后一步有三种方法，最后一步分别走1步，共f(n-1)种,\n",
    "        #最后一步走2步，共f(n-2)种。最后一步走3步，共f(n-3)种\n",
    "        #因此f(n)=f(n-1)+f(n-2)+f(n-3) f(0)=1,f(1)=1,f(2)=2\n",
    "        if n==1:\n",
    "            return 1\n",
    "        if n==2:\n",
    "            return 2\n",
    "        dp=[1]*(n+1)\n",
    "        dp[2]=2\n",
    "        for i in range(3,n+1):\n",
    "            dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000007\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        dp[2] = 2\n",
    "        for i in range(3,n+1):\n",
    "            dp[i] = (dp[i-1]+dp[i-2]+dp[i-3]) % 1000000007\n",
    "        return dp[-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        dp=[0]*1000001\n",
    "        dp[0]=1\n",
    "        dp[1]=1\n",
    "        dp[2]=2\n",
    "        for i in range(3,n+1):\n",
    "            dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000007\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        dp = [0,1,2,4,]+[0]*(n+4)\n",
    "        for i in range(4,n+1):\n",
    "            dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%1000000007\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        l = [0,1,2,4]+[0]*(n+4)\n",
    "        for i in range(4,n+1):\n",
    "            l[i] = (l[i-1]+l[i-2]+l[i-3])%1000000007\n",
    "        return l[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        res = [0]*n\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2\n",
    "        if n == 3:\n",
    "            return 4\n",
    "        res[0] = 1\n",
    "        res[1] = 2\n",
    "        res[2] = 4\n",
    "        for i in range(3,n):\n",
    "            res[i] = (res[i-1] + res[i-2] + res[i-3])%1000000007\n",
    "        return res[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        elif n == 3:\n",
    "            return 4\n",
    "        \n",
    "        dp = [0] + [0] * n\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        dp[2] = 2                              \n",
    "        dp[3] = 4\n",
    "\n",
    "\n",
    "        for i in range(4, n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\n",
    "            dp[i] = dp[i] % 1000000007\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToStep(self, n: int) -> int:\n",
    "        dp = [1, 2, 4]\n",
    "        if n <= 3:\n",
    "            return dp[n - 1]\n",
    "        for i in range(4, n + 1):\n",
    "            dp.append((dp[i - 2] + dp[i - 3] +  dp[i - 4]) % 1000000007)\n",
    "        return dp[-1] % 1000000007\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
